﻿#include<vector>
#include <deque>

using namespace std;


/*
1687. 从仓库到码头运输箱子
你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。

给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [ports​​i​, weighti] 。

ports​​i 表示第 i 个箱子需要送达的码头， weightsi 是第 i 个箱子的重量。
portsCount 是码头的数目。
maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。
箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：

卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。
对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。
卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。
卡车在将所有箱子运输并卸货后，最后必须回到仓库。

请你返回将所有箱子送到相应码头的 最少行程 次数。
*/
class Solution {
public:
	int n;
	vector<int> s;

	int cost(int left, int right)
	{
		if (s[left] != s[left + 1])
		{
			return s[right] - s[left];
		}
		return s[right] - s[left] + 1;
	}

	int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
		n = boxes.size();
		s.resize(n + 2);
		for (int i = 1; i <= n; i++)
		{
			s[i] = s[i - 1];
			if (i == 1 || boxes[i - 1][0] != boxes[i - 2][0])
				s[i]++;
		}

		vector<int> f(n + 1);
		deque<int> q;
		q.push_back(0);
		for (int i = 1, j = 1, w = 0; i <= n; i++)
		{
			w += boxes[i - 1][1];
			while (w > maxWeight || i - j + 1 > maxBoxes)
			{
				w -= boxes[j - 1][1];
				j++;
			}
			while (q.front() < j - 1) q.pop_front();
			int k = q.front();
			f[i] = f[k] + cost(k, i) + 1;
			while (q.size() && f[q.back()] >= f[i] + cost(i, i + 1) - cost(q.back(), i + 1))
				q.pop_back();
			q.push_back(i);
		}
		return f[n];
	}
};
